package com.wangjie.doublepointer;

/**
 * @author jieshao
 * @date 2022/4/29 14:57
 */
public class Test12 {
    public static void main(String[] args) {
        ListNode t5 = new ListNode(5, null);
        ListNode t4 = new ListNode(4, t5);
        ListNode t3 = new ListNode(3, t4);
        ListNode t2 = new ListNode(2, t3);
        ListNode t1 = new ListNode(1, t2);
        System.out.println("反转前：");
        for (ListNode p = t1; p != null; p = p.next) {
            System.out.println(p.val);
        }

        ListNode head = reverseBetween(t1, 2, 4);

        System.out.println("反转后：");
        for (ListNode p = head; p != null; p = p.next) {
            System.out.println(p.val);
        }
    }

    /**
     * 92. 反转链表的一部分(迭代实现)
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        // 第一步，从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点(前驱节点)
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第二步，从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第三步，切断出一个子链表
        ListNode leftNode = pre.next;
        // 后驱节点
        ListNode cur = rightNode.next;

        // 第四步，切断链接
        pre.next = null;
        rightNode.next = null;

        // 第五步，反转链表的子区间
        reverse(leftNode);

        // 第六步，接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = cur;

        return dummy.next;
    }

    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}